package com.xiaoyg.algorithm;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class CyscleLink {

    static class ListNode{
        int val;
        ListNode next;

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }

        public ListNode(int val, ListNode next){
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 快慢指针，快指针移动两部，满指针移动一步
     * @param head
     * @return
     */
    public static boolean hasCycle(ListNode head){
        if (head == null || head.next == null){
            return false;
        }
        ListNode slowPtr = head,fastPtr = head;
        while (fastPtr!=null && fastPtr.next.next != null){
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
            if (slowPtr == fastPtr){
                return true;
            }
        }
        return false;
    }


    public static ListNode hasCycleFirstNode(ListNode head){
        if (head == null || head.next == null){
            return null;
        }
        boolean isHasCycle = false;
        ListNode slowPtr = head,fastPtr = head;
        while (fastPtr!=null && fastPtr.next.next != null){
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
            if (slowPtr == fastPtr){
                isHasCycle = true;
                break;
            }
        }
        if (isHasCycle){
            slowPtr = head;
            while (slowPtr != fastPtr) {
                fastPtr = fastPtr.next;
                slowPtr = slowPtr.next;
            }
            return slowPtr;
        }
        return null;
    }



    public static boolean hasCycleBySet(ListNode head){
        if (head == null || head.next == null){
            return false;
        }
        Set<ListNode> set = new HashSet<>();

        ListNode ptr = head;
        while (ptr != null && ptr.next.next != null){
            ptr = ptr.next;
            if (set.contains(ptr)){
                return true;
            }
            set.add(ptr);
        }
        return false;
    }

    public static void main(String[] args) {
       ListNode node4 = new ListNode(-4, null);
       ListNode node3 = new ListNode(0, node4);
       ListNode node2 = new ListNode(2, node3);
       ListNode node1 = new ListNode(3, node2);
        node4.setNext(node2);
        System.out.println(hasCycleFirstNode(node1).val);
//
    }









}
